package org.jiang.springbootdemo.demos.web.test.programmingTest;

import java.util.*;

// 待处理
public class ValidBrackets {
    // 偶数个 + 位置关系
    // 从第一个 ')'、'}'、']'开始
    // 修改前
    public static boolean isValid(String s) {
        // 偶数个才有可能配对
        int len = s.length();
        if (len % 2 != 0) return false;
        int tmp = 0, size = 0;
        Map<Character, Character> map = new HashMap<Character, Character>(){{
            put('(', ')');
            put('[', ']');
            put('{', '}');
        }};
        char ch;
        // 还未配对的'('、'['、'{'下标
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            size = list.size() - 1;
            ch = s.charAt(i);
            if (ch == ')' || ch == '}' || ch == ']') {
                if (i == 0 || size < 0) {
                    // 必须以'('、'['、'{'开头
                    return false;
                }
                tmp = list.get(size);
                if (tmp >= 0 && ch == map.get(s.charAt(tmp))) {
                    // 保证顺序匹配
                    list.remove(size);
                } else {
                    return false;
                }
            } else {
                list.add(i);
            }
        }
        return list.isEmpty();
    }

    // 修改后
//    public static boolean isValid(String s) {
//        int n = s.length();
//        if (n % 2 == 1) {
//            return false;
//        }
//        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
//            put(')', '(');
//            put(']', '[');
//            put('}', '{');
//        }};
//        Stack<Character> stack = new Stack<>();
//        char ch;
//        for (int i = 0; i < n; i++) {
//            ch = s.charAt(i);
//            if (pairs.containsKey(ch)) {
//                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
//                    return false;
//                }
//                stack.pop();
//            } else {
//                stack.push(ch);
//            }
//        }
//        return stack.isEmpty();
//    }

    public static void main(String[] args) {
        System.out.println(isValid("([{}])"));// true
        System.out.println(isValid("()[]{}"));// true
        System.out.println(isValid("}("));// false
        System.out.println(isValid("([}}])"));// false
        System.out.println(isValid("(]"));// false
        System.out.println(isValid("(([]){})"));// true
        System.out.println(isValid("()"));// true
        System.out.println(isValid("[({])}"));// false
        System.out.println(isValid("[({(())}[()])]"));// true
        System.out.println(isValid("(("));// false
        System.out.println(isValid("(){}}{"));// false
    }
}